"""
基数排序：
    - 时间复杂度： O(kn)
    - 空间复杂度： O(k + n)
    - k表示数字的位数
"""

from SortingAlgorithm.cal_time.cal_time import cal_time
from SortingAlgorithm.quick_sort1 import quick_sort


@cal_time(name="基数的排序时间")
def radix_sort(li):
    max_num = max(li)
    it = 0
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            digit = (var // 10**it) % 10
            buckets[digit].append(var)
        # 分桶完成
        li.clear()
        for buc in buckets:
            li.extend(buc)

        it += 1


if __name__ == "__main__":
    import random, copy
    li = [random.randint(0, 100000000000) for _ in range(10000)]

    li1 = copy.deepcopy(li)

    radix_sort(li)
    quick_sort(li1)
